package com.linwen.excise.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName _101对称二叉树
 * @Description TODO
 * @Author zero
 * @DATE 2024/4/28 2:46 AM
 * @Version 1.0
 */
public class _101对称二叉树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(isSymmetric2(root));
    }


    public static boolean isSymmetric2(TreeNode root) {
        if (root == null) {
            return true;
        }
        LinkedList<LinkedList<TreeNode>> queueLevel = new LinkedList<>();
        Queue<Queue<TreeNode>> queue = new LinkedList<>();
        Queue<TreeNode> rootQueue = new LinkedList<>();
        rootQueue.add(root);
        queue.add(rootQueue);
        while (!queue.isEmpty()){
            Queue<TreeNode> poll = queue.poll();
            Queue<TreeNode> tempPool = new LinkedList<>();
            LinkedList<TreeNode> level = new LinkedList<>();
            while (!poll.isEmpty()){
                TreeNode node = poll.poll();
                if(node!=null){
                    tempPool.add(node.left);
                    tempPool.add(node.right);
                    level.add(node.left);
                    level.add(node.right);
                }
            }
            if(!tempPool.isEmpty()){
                queue.add(tempPool);
                queueLevel.add(level);
            }
        }

        while (!queueLevel.isEmpty()){
            LinkedList<TreeNode> poll = queueLevel.poll();
            while (!poll.isEmpty()){
                TreeNode left = poll.pollFirst();
                TreeNode right = poll.pollLast();
                if(left == null && right == null){
                    continue;
                }
                if(left == null || right == null){
                    return false;
                }
                if(left.val != right.val){
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetric(root.left,root.right);
    }

    public static boolean isSymmetric(TreeNode left, TreeNode right) {
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }
}
